/*
 * @lc app=leetcode.cn id=300 lang=javascript
 *
 * [300] 最长递增子序列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let length = nums.length
  let dp = new Array(length).fill(1)

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }

  return Math.max(...dp)
}
// @lc code=end

// 状态定义
// dp[i]：表示以nums[i]为当前最长递增子序列尾元素的长度
// 转移方程
// 当 nums[i] > nums[j] 时，
// nums[i]可以作为前1个是最长的递增子序列 dp[j] 新的尾元素，
// 而组成新的相对于dp[i]能够拼接的更长的递增子序列：dp[i] = dp[j] + 1；
// 如图：dp[0] 和 dp[1]
// 因为新的dp[i]能够拼接的最长长度取决于nums[i]这个新的尾元素，而这个nums[i]不一定大于nums[j]，所以也不一定大于dp[j]
// 比如dp[j] = 4，nums[i] < nums[j] && nums[i] > nums[z] && dp[z] = 2 && z < i && j < i
// 则此时，dp[i] = dp[z] + 1 = 3，不能拼接在dp[j]的后面，不是一定的
// 如图 dp[3] > dp[4] && nums[4] < nums[3]
// 那么在i~j之间，最大的递增子序列 = Max(dp[i],dp[j]+1)
// 即方程为：dp[i] = Max(dp[i],dp[j]+1)
// 当 nums[i] <= nums[j] 时，
// 是下降了，不满足上升，跳过继续遍历下一个
// 由此可知，每一阶段都有相邻两个递增子序列，那么所有递增子序列的最大值为：
// 1、求解过程中，维护一个变量max，如当前解法中第一种写法
// 2、在最后for循环遍历求最大值或者用库函数求数组中的最大值，如当前解法中第二种写法
// 初始化
// 为1，每个元素本身也是一个子序列，长度为1
